package com.zofer.study.tree;

/**
 * @description 获取树最大深度和最小深度
 *
 * @date: 2020/10/15 11:22
 */
public class TreeDepth {

    public static void main(String[] args) {
        // 第五层
        TreeNode left211 = new TreeNode(0);
        TreeNode right211 = new TreeNode(0);

        // 第四层
        TreeNode left21 = new TreeNode(0);
        left21.left = left211;
        left21.right = right211;

        // 第三层
        TreeNode left111 = new TreeNode(0);
        left111.left = left21;

        TreeNode right111 = new TreeNode(0);

        TreeNode left121 = new TreeNode(0);
        TreeNode right121 = new TreeNode(0);

        // 第二层
        TreeNode left11 = new TreeNode(0);
        left11.left = left111;
        left11.right = right111;

        TreeNode right12 = new TreeNode(0);
        right12.left = left121;
        right12.right = right121;

        // 第一层
        TreeNode root = new TreeNode(0);
        root.left = left11;
        root.right = right12;

        //树最大深度
        int treeMaxDepth = getTreeMaxDepth(root);
        System.out.println("树最大深度:"+treeMaxDepth);

        System.out.println("======================");

        //树最小深度
        int treeMinDepth = getTreeMinDepth(root);
        System.out.println("树最小深度:"+treeMinDepth);
    }


    /**
     * 获取树最大深度
     */
    public static int getTreeMaxDepth(TreeNode treeNode){
        if (treeNode == null){
            return 0;
        }else {
            int left = getTreeMaxDepth(treeNode.left);
            int right = getTreeMaxDepth(treeNode.right);
            return 1 + Math.max(left,right);
        }
    }


    /**
     * 获取树最小深度
     */
    public static int getTreeMinDepth(TreeNode treeNode){
        if (treeNode == null){
            return 0;
        }else {
            int left = getTreeMinDepth(treeNode.left);
            int right = getTreeMinDepth(treeNode.right);
            return 1 + Math.min(left,right);
        }
    }
}
